/*
Copyright 2008, 2009 Joonas Lehtolahti

This file is part of Shared Datatypes and Utilities.

Shared Datatypes and Utilities is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

Shared Datatypes and Utilities is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License
along with Shared Datatypes and Utilities.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef _TREE_H_
#define _TREE_H_

#include "shared_def.h"

/*
  General tree node for all tree types
  Members:
  x       void pointer to the contents of this node
  parent  pointer to the parent node
  left    pointer to left child node
  right   pointer to right child/sibling node
  height  the height of this subtree
*/
typedef struct _treenode
{
  void *              x;
  struct _treenode *  parent;
  struct _treenode *  left;
  struct _treenode *  right;
  int                 height;
}TreeNode;

/* BinaryTree */
typedef struct _btree
{
  TreeNode *   root;
  CMPFUNC  *cmpfunc;
}BTree;


/* Binary Tree creation with comparator function as parameter */
DLLEXPORT(BTree*) newBTree(CMPFUNC*);

/* Binary Tree deletion with automatic memory freeing */
DLLEXPORT(void) freeBTree(BTree*,FREEFUNC*);
DLLEXPORT(void) freeBTreeNode(TreeNode*,FREEFUNC*);

/* Binary Tree find function */
DLLEXPORT(TreeNode*) BTreeFind(BTree*,void*);

/* AVL Tree adding functions */
DLLEXPORT(TreeNode*) BTreeAdd(BTree*,void*);
DLLEXPORT(void*) BTreeReplace(BTree *tree, void *x);
DLLEXPORT(TreeNode*) BTreeFindOrAdd(BTree *tree, void *x);

/* AVL Tree deleting function */
DLLEXPORT(int) BTreeDel(BTree*,TreeNode*);

/* Binary Tree iteration functions */
DLLEXPORT(TreeNode*) iterateTree(BTree *tree);
DLLEXPORT(TreeNode*) iterateTreeNext(TreeNode *orig);

DLLEXPORT(void) BTree_debug_dump(BTree *tree);

#endif
